/**
 * LCP 07. 传递信息
 */
public class NumWays {
    public int numWays(int n, int[][] relation, int k) {
//        int[][] dp = new int[k + 1][n]; // 经过i轮到达n号玩家的方案数
//        // 最开始在0号玩家这里，所以经过0步到达零号玩家的方案数是一
//        for (int i = 0; i < n; i++) {
//            dp[0][i] = i != 0 ? 0 : 1;
//        }
//        for (int i = 0; i < k; i++) {
//            for (int[] rel : relation) {
//                int a = rel[0], b = rel[1];
//                dp[i + 1][b] += dp[i][a];
//            }
//        }
//        return dp[k][n - 1];

        // 优化
        int[] dp = new int[n]; // 观察上边发现后一个的值只与i有关系
        dp[0] = 1;
        for (int i = 0; i < k; i++) {
            int[] next = new int[n];
            for (int[] rel : relation) {
                int a = rel[0], b = rel[1];
                next[b] += dp[a];
            }
            dp = next;
        }
        return dp[n - 1];
    }
}
